|
週次 |
日期 |
單元主題 |
|
Week 1 |
2/24 |
Lesson 1: Basic complexity classes (online) |
|
Week 2 |
3/3 |
Lesson 2: NP-complete problems (online) |
|
Week 3 |
3/10 |
Lesson 3: More on the class NP (online) |
|
Week 4 |
3/17 |
No lesson |
|
Week 5 |
3/24 |
Lesson 4: The class NL and PSPACE |
|
Week 6 |
3/31 |
Lesson 5: Alternating Turing machines
(Homework 1 due, homework 2 out) |
|
Week 7 |
4/7 |
Lesson 6: The class #P |
|
Week 8 |
4/14 |
Lesson 7: Boolean circuits |
|
Week 9 |
4/21 |
Lesson 8: Probabilistic Turing machines |
|
Week 10 |
4/28 |
No lesson |
|
Week 11 |
5/5 |
Lesson 9: Probabilistic reductions
(homework 2 due) |
|
Week 12 |
5/12 |
Lesson 10: Toda's theorem |
|
Week 13 |
5/19 |
Lesson 11: Interactive proofs
|
|
Week 14 |
5/26 |
Lesson 12: IP and PSPACE |
|
Week 15 |
6/2 |
Lesson 13: Probabilistic checkable proofs
(homework 3 due) |
|
Week 16 |
6/9 |
No lesson |